| r6 ➤ r7 |
| 129 | [[시간 복잡도#s-3.3|마스터 정리]]을를 사용하면 [math(\Theta(n\log n))]이라는 것을 알 수 있다. |
| 132 | ====의사 코드==== |
| 133 | 다음은 퀵 정렬의 의미를 간단히 서술한 코드이다. |
| 134 | |
| 135 | {{{#!syntax java |
| 136 | quickSort(A[], p, r): |
| 137 | if (p < r) |
| 138 | q ← partition (A, p, r) |
| 139 | quickSort(A, p, q-1) |
| 140 | quickSort(A, q+1, r) |
| 141 | |
| 142 | partition(A[], p, r): |
| 143 | 배열 A[p…r]의 원소들을 기준 원소인 A[r]을 기준으로 양쪽으로 재배치하고 |
| 144 | 기준 원소가 자리한 위치를 리턴한다. |
| 145 | }}} |
| 146 | 다음은 분할 함수(partition)을 풀어 서술한 코드이다. |
| 147 | |
| 148 | {{{#!syntax java |
| 149 | partition(A[], p, r): |
| 150 | x ← A[r] |
| 151 | i ← p-1 |
| 152 | for j ← p to r-1 |
| 153 | if (A[j] < x) |
| 154 | A[++i] ↔ A[j] |
| 155 | A[i+1] ↔ A[r] |
| 156 | return i+1 |
| 157 | }}} |
| 158 | ====분석==== |
| 159 | [[시간 복잡도]]의 점근적 형태가 상황에 따라 달라진다. 우선 분할은 배열을 왼쪽부터 끝까지 한 번 훑어나가는 작업이므로 [math(\Theta(n))]의 시간이 든다. |
| 160 | * '''최선의 경우''': 항상 반반씩 균등하게 분할될 때이므로, 점화식이 [math(T(n)=2T(\frac{n}{2})+\Theta(n))]이 된다. 즉 [[시간 복잡도#s-3.3|마스터 정리]]를 사용하면 [math(\Theta(n\log n))]이라는 것을 알 수 있다. |
| 161 | * '''최악의 경우''': 계속해서 한쪽은 하나도 없고 다른 쪽에 다 몰리도록 분할이 되는 경우이다. 이 때는 점화식이 [math(T(n)=T(n-1)+\Theta(n))]이므로 [[시간 복잡도#s-3.1|반복 대치]]를 사용하면 [math(\Theta(n\log n))]라는 것을 알 수 있다. |
| 162 | * '''평균적인 경우''': 크기 [math(n)]인 배열의 피벗이 [math(i)]등이면 1구역과 2구역의 크기는 [math(i-1:n-1)]가 된다. 따라서 점화식은 [math(T(n)=T(i-1)+T(n-i)+\Theta(n))]이고, 평균 시간으로 나타내면 [math(T(n)=\frac{1}{n}\sum_{i=1}^ n ({T(i-1)+T(n-i)})+\Theta(n))]. [[시간 복잡도#s-3.2|추정 후 증명]]을 사용하면 [math(\Theta(n\log n))]라는 것을 알 수 있다. 이 증명은 하위 문단으로 따로 서술한다. |
| 163 | =====평균적인 경우의 증명===== |
| 164 | [math(T(2) \leq c2\log 2)]를 만족하도록 충분히 큰 [math(c)]를 잡을 수 있으므로, [math(2<k<n)]인 모든 [math(k)]에 대해 [math(T(k) \leq ck\log k)]가 성립한다고 가정하자. |
| 165 | |
| 166 | [math(T(n)=\frac{1}{n}\sum_{i=1}^ n ({T(i-1)+T(n-i)})+\Theta(n))] |
| 167 | [math(=\frac{2}{n}\sum_{k=1}^ {n-1} T(k)+\Theta(n))] |
| 168 | [math(=\frac{2}{n}\sum_{k=2}^ {n-1} T(k)+\Theta(n))][* log를 사용하기 위해 약간의 트릭을 쓴 것이다. log 1 = 0이므로 부등식을 만들 수 없어 k가 0인 경우와 1인 경우를 제외시켰다. 그런데도 부등호 대신 등호를 사용한 것은 이 두 항, 즉 T(0)과 T(1)을 Θ(n)에 집어넣어 버렸기 때문이다. 이러한 기법을 '흡수'라고 한다. 흡수는 상수 번만 해야지 그렇지 않으면 시간복잡도 분석에 오류가 생긴다. 여기에서는 단 한 번 하는 것이 고작이므로 여전히 Θ(n)는 일차함수다.] |
| 169 | [math(\leq\frac{2}{n}\sum_{k=2}^ {n-1} ck \log k+\Theta(n))] |
| 170 | [math(\leq\frac{2c}{n}\sum_{k=2}^ {n-1} (\frac{1}{2}n^2 \log n -\frac{1}{8}n^2)+\Theta(n))] |
| 171 | [math(=cn\log n - \frac{cn}{4}+\Theta(n))] |
| 172 | [math(\leq cn \log n)] |
| 173 | |
| 174 | 4번째 줄에서 5번째 줄로 넘어가는 과정은 다음과 같다. |
| 175 | [math(\sum_{k=1}^ {n-1} k \log k = \sum_{k=1}^ {⌈n/2⌉-1} k \log k + \sum_{k=⌈n/2⌉}^ {n-1} k \log k)] |
| 176 | [math(\sum_{k=1}^ {n-1} k \log k \leq (\log n-1) \sum_{k=1}^ {⌈n/2⌉-1} k + \log n\sum_{k=⌈n/2⌉}^ {n-1} k )][* 오른쪽 첫 번째 항의 log k는 log (n/2)=log n - 1로 상한을 잡을 수 있고, 두 번째 항의 log k는 log n으로 상한을 잡을 수 있기 때문이다.] |
| 177 | [math(= \log n \sum_{k=1}^ {n-1} k - \sum_{k=1}^ {⌈n/2⌉-1} k )] |
| 178 | [math(\leq \frac{1}{2}n^2 \log n - \frac{1}{8}n^2)] |
| 179 | [math(\sum_{k=2}^ {n-1} k \log k \leq \sum_{k=1}^ {n-1} k \log k)]이므로 [math(\sum_{k=2}^ {n-1} k \log k \leq \frac{1}{2}n^2 \log n - \frac{1}{8}n^2)]이다. |
